package 力扣._15_三数之和;

import java.util.*;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //先排序了  ijk互不相等，且三元组的值不重复
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int i = 0, j = 0, k = 0;
        for (i = 0; i < nums.length - 2; i++) {
            //要和上一次枚举的值不同
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            for (j = i + 1, k = nums.length - 1; j < k; ) { //将j,k使用双指针遍历
                if (nums[i] + nums[k - 1] + nums[k] < 0) //最大值小于0，则只有i++，才有可能让值为0
                    break;
                else if (nums[i] + nums[i + 1] + nums[k] > 0)   //最小值大于0，则只有k--，才有可能让值为0
                    k--;

                if (k < nums.length - 1 && nums[k] == nums[k + 1])   //避免k重复
                    k--;
                else if (j > i + 1 && nums[j] == nums[j - 1])   //避免k重复
                    j++;
                else if (nums[i] + nums[j] + nums[k] < 0)
                    j++;
                else if (nums[i] + nums[j] + nums[k] > 0)
                    k--;
                else {
                    List<Integer> t = new ArrayList<>();
                    t.add(nums[i]);
                    t.add(nums[j]);
                    t.add(nums[k]);
                    result.add(t);
                    j++;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3,0,-2,-1,1,2};
        List<List<Integer>> lists = new Solution().threeSum(nums);
        System.out.println(lists);
    }
}
